#include <iostream>

using namespace std;

class Solution {
public:
    // 空间复杂度为 O(n)，时间复杂度为 O(n * sqrt(n))
    // 这里是完全背包问题，体积为 n，价值为 1
    int numSquares(int n) {
        int f[n + 1];
        // 首先初始化 f[0]，f[0] 代表的是容量为 0 的背包，
        // 此时放不下任何物品，因此背包最大的价值为 0
        f[0] = 0;

        for (int i = 1; i <= n; i++) {
            f[i] = INT_MAX;
            // for (int j = weight[i]; j <= W; j++)
            // 体积（完全平方数）为 1 ~ j * j (j * j <= i)
            for (int j = 1; j * j <= i; j++) {
                // f[j] = max(f[j], f[j - weight[i]] + value[i]);
                // 代入完全背包问题的状态转移模板即可
                f[i] = min(f[i], f[i - j * j] + 1);
            }
        }

        return f[n];
    }
};